package com.mingqi.hw.test91100;

/**  【猜密码】
 * 小杨申请了一个保密柜，但是他忘记了密码。只记得密码都是数字，而且所有数字都是不重复的。请你根据他记住的数字范围和密码的最小数字数量，帮他算下有哪些可能的组合，规则如下：
 * 1、输出的组合都是从可选的数字范围中选取的，且不能重复；
 * 2、输出的密码数字要按照从小到大的顺序排列，密码组合需要按照字母顺序，从小到大的顺序排序。
 * 3、输出的每一个组合的数字的数量要大于等于密码最小数字数量；
 * 4、如果可能的组合为空，则返回“None”
 * 输入描述:
 * 1、输入的第一行是可能的密码数字列表，数字间以半角逗号分隔
 * 2、输入的第二行是密码最小数字数量
 * 输出描述:
 * 可能的密码组合，每种组合显示成一行，每个组合内部的数字以半角逗号分隔，从小到大的顺序排列。
 * 输出的组合间需要按照字典序排序。
 * 比如：
 * 2,3,4放到2,4的前面
 * 示例1
 * 输入
 * 2,3,4
 * 2
 * 输出
 * 2,3
 * 2,3,4
 * 2,4
 * 3,4
 * 说明
 * 最小密码数量是两个，可能有三种组合：
 * 2,3
 * 2,4
 * 3,4
 * 三个密码有一种：
 * 2,3,4
 * 示例2
 * 输入
 * 2,0
 * 1
 * 输出
 * 0
 * 0,2
 * 2
 * 说明
 * 可能的密码组合，一个的有两种 ：
 * 0
 * 2
 * 两个的有一个：
 * 0,2
 * 备注:
 * 字典序是指按照单词出现在字典的顺序进行排序的方法，比如：
 * a排在b前
 * a排在ab前
 * ab排在ac前
 * ac排在aca前
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class ZT100 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] numbers = scanner.nextLine().split(",");
        int minLength = Integer.parseInt(scanner.nextLine());
        scanner.close();

        // 将数字列表转换为整数数组，并排序
        Integer[] sortedNumbers = new Integer[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            sortedNumbers[i] = Integer.parseInt(numbers[i]);
        }
        Arrays.sort(sortedNumbers);

        // 调用生成密码组合的方法
        List<List<Integer>> combinations = generatePasswordCombinations(sortedNumbers, minLength, new ArrayList<>(), 0);

        // 如果没有组合，输出"None"
        if (combinations.isEmpty()) {
            System.out.println("None");
        } else {
            // 遍历并打印所有组合
            for (List<Integer> combination : combinations) {
                String output = String.join(",", combination.stream().map(Object::toString).toArray(String[]::new));
                System.out.println(output);
            }
        }
    }

    private static List<List<Integer>> generatePasswordCombinations(Integer[] numbers, int minLength, List<Integer> current, int index) {
        List<List<Integer>> combinations = new ArrayList<>();

        // 如果当前组合的长度大于等于最小长度，则添加到结果中
        if (current.size() >= minLength) {
            combinations.add(new ArrayList<>(current));
        }

        // 从当前索引开始遍历剩余的数字
        for (int i = index; i < numbers.length; i++) {
            // 如果不是第一个数字，并且与前一个数字相同，则跳过（确保不重复）
            if (i > index && numbers[i] == numbers[i - 1]) {
                continue;
            }

            // 将当前数字添加到组合中
            current.add(numbers[i]);

            // 递归调用，生成以当前数字为起点的后续组合
            combinations.addAll(generatePasswordCombinations(numbers, minLength, current, i + 1));

            // 回溯，移除当前数字以生成其他组合
            current.remove(current.size() - 1);
        }

        return combinations;
    }
}
